package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.Collections;

public class ZigZagOrderTraversal {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(root == null)
            return res;
            
        ArrayList<TreeNode> level = new ArrayList<TreeNode>();
        level.add(root);
        
        boolean reverse = false;
        while(level.size() > 0)
        {
            ArrayList<TreeNode> newLevel = new ArrayList<TreeNode>();
            ArrayList<Integer> levelVal = new ArrayList<Integer>();
            
            for(TreeNode node : level)
            {
                if(node.left != null)
                    newLevel.add(node.left);
                if(node.right != null)
                    newLevel.add(node.right);
                
                levelVal.add(node.val);
            }
            level = newLevel;
            
            if(reverse)
                Collections.reverse(levelVal);
            res.add(levelVal);
            reverse = !reverse;
        }
        
        return res;
    }
}
